%%% xytree.sty  -- a bunch of macros for typesetting tree-like
%%%                structures with \Xy-Pic.
%%%
%%% These are presently very rough macros, probably not yet suited for
%%% use by anyone else...
%%%
%%% BUGS: (1) The more a tree is unbalanced, the more connectors won't
%%% match exactly at vertices. This is due to a discrepancy between
%%% the placement of parent node, and the position \Xy-Pic assigns to
%%% the "UC" corner of an object; I haven't yet figured out how to
%%% guess the latter.
%%%       (2) \Xy-Pic needs '@' to be of category 12 (other), so we
%%% cannot use it in package-private names---as is customary in
%%% LaTeX---unless we do some wizardry (?); I resort to using an
%%% uppercase prefix "XYT" and very long names, in the hope none will
%%% ever clash...  
%%%
%%% $Id: xytree.sty,v 1.1 2006/05/25 07:02:56 rmurri Exp $ 
%%%

%%
%% Lengths
%%
\newlength{\treegap}       % separate leaves by this amount of white space
\setlength{\treegap}{24pt}  

\newlength{\treeheight}    % distance between node and row of leaves
\setlength{\treeheight}{24pt}

%%
%% Counters
%%
\newcounter{XYTnode}  % for naming nodes (= non-terminal vertices)
\newcounter{XYTleaf}  % for naming leaves (= terminal vertices)

%%
%% \ifXYTfirst -- are we typesetting the first node (or leaf) of a branch?
%%
%% We need a LIFO of \ifXYTfirst states in order to correctly handle
%% nesting of branches. This is presently implemented converting
%% \ifXYTfirst status to 1-character tokens '0' or '1' and saving these
%% in a \xdef'ed macro. Sure not the best way to do that, but I'm too
%% lazy to go and reread the relevant part of the \TeX book.
%%
\newif\ifXYTfirst

\newcommand{\XYTbeginbranch}{%
  % push \ifXYTfirst status into the stack: the \xdef will expand the
  % macro definition while defining, so \XYTfirststack will have a '0'
  % or '1' prepended.
  \xdef\XYTfirststack{\ifXYTfirst1\else0\fi%
    \XYTfirststack}%
  % effectively begin the branch: next {leaf,node} is the first.
  \XYTfirsttrue%
}

\newcommand{\XYTendbranch}{%
  % call a macro with a delimited argument, so that first token will
  % be used to restore \ifXYTfirst status, and rest will go into
  % \XYTfirststack again.
  \expandafter\XYTfirstpop\XYTfirststack-%
}
\def\XYTfirstpop#1#2-{%
  \if1#1%
    \XYTfirsttrue%
  \else%
    \XYTfirstfalse%
  \fi%
  \xdef\XYTfirststack{#2}%
}

\makeatother % \Xy-Pic needs user-mode catcodes (cf. xyrefer, p. 4)

%%
%% \XYTleavegap -- leave a gap before non-first leaves
%%
\newcommand{\XYTleavegap}{%
  \ifXYTfirst%
    \relax%
  \else%
    \POS +/r\treegap/%
  \fi%
}

%%
%% \XYTmarkiffirst -- define <pos> "first" if first-node-of-row
%%
\newcommand{\XYTmarkiffirst}{%
  \ifXYTfirst\POS s0="first"\fi% this node is first node
  \XYTfirstfalse% next node is not first anyway
}


%%
%% \leaf{LABEL} -- make a leaf labeled with material in LABEL
%%
%% Adds a leaf to a branch. The material in LABEL is typeset as a
%% \Xy-Pic object.
%%
\newcommand{\leaf}[1]{%  nodo terminale
  \stepcounter{XYTleaf}% advance XYTleaf by 1
  \XYTleavegap% leave a gap if non first
  % save UC position into the \Xy-Pic stack, so later we map over all this
  % positions to draw lines to the parent node.
  \POS @+{*+!U{#1}+UC},s0="\treename LEAF\theXYTleaf"%
  \XYTmarkiffirst%
  \ignorespaces
}

%%
%% \bleaf{LABEL} -- make a leaf with boxed label
%%
%% Adds a leaf to a branch, with boxed label. Cf. \leaf
%%
\newcommand{\bleaf}[1]{% nodo terminale, riquadrato
  \stepcounter{XYTleaf}% advance XYTleaf by 1
  \XYTleavegap%
  \POS @+{*+!U[F]{#1}+UC},s0="\treename LEAF\theXYTleaf"%
  \XYTmarkiffirst%
  \ignorespaces
}

%%
%% \fleaf{LABEL}{FRAME} -- make a leaf with framed label
%%
%% Adds a leaf to a branch, with framed label; LABEL may be any valid
%% TeX material for enclosing in \Xy-Pic \drop{...} command; FRAME is
%% any legal \frm{...} argument.
%%
\newcommand{\fleaf}[2]{% nodo terminale, cerchiato
  \stepcounter{XYTleaf}% advance XYTleaf by 1
  \XYTleavegap%
  \POS @+{*+!U[F#1]{#1}+UC},s0="\treename LEAF\theXYTleaf"%
  \XYTmarkiffirst%
  \ignorespaces
}


%%
%% \gap[LABEL] -- leave a space, optionally typeset label LABEL
%%
%% Leaves a gap between branches. The material in LABEL is typeset as a
%% \Xy-Pic object.
%%
\newcommand{\gap}[1][]{%  nodo terminale
  \stepcounter{XYTleaf}% advance XYTleaf by 1
  \XYTleavegap% leave a gap if non first
  % save UC position into the \Xy-Pic stack, so later we map over all this
  % positions to draw lines to the parent node.
  \POS *+!U{#1}+UC%
  \XYTmarkiffirst%
  \ignorespaces
}

%%
%% \branch[DIR]{<NODES>} -- make a branch of a tree
%%
%% Makes a branch, with parent node decorated by \bullet. The argument
%% is a whitespace-separated list of other \branch or \leaf
%% commands. The optional argument DIR is a directional for lines
%% connecting parent and children nodes, in a form suitable for use
%% \Xy-Pic's command \dir{}; defaults to '-' (continuos line).
%%
\newcommand{\branch}[2][-]{%
  \stepcounter{XYTnode}% advance XYTnode by 1
  \XYTleavegap% leave space if this is not the first node
  \XYTbeginbranch% save \ifXYTfirst etc.
  % a \begin{branch}...\end{branch} syntax wouyld be more adequate,
  % perhaps, but \xybox needs its material as an argument and I don't
  % know how to circumvent this.
  \POS @+{*!U\xybox{%
    @i% start a new \Xy-Pic stack for local use
    #2% typeset <NODES>
    \POS;"first"**\dir{}?% find the midpoint of the row of leaves
    +/u\treeheight/*-{\bullet}="parent"% go up and typeset a \bullet
    @@{;"parent"**\dir{#1}},% map over saved nodes: draw straight line
                            % to parent node.
  }+UC}="\treename NODE\theXYTnode"%
  \XYTendbranch% pop \ifXYTfirst status
  \XYTmarkiffirst%
  \ignorespaces
}

%%
%% \bbranch[DIR]{LABEL}{<NODES>} -- make a branch with boxed parent node
%%
%% Makes a branch. Parent node is decorated by a boxed LABEL. (Cf. \branch)
%%
\newcommand{\bbranch}[3][-]{%
  \stepcounter{XYTnode}%
  \XYTleavegap%
  \XYTbeginbranch%
  \POS @+{*!U\xybox{%
    @i%
    #3%
    \POS;"first"**\dir{}%
    ?+/u\treeheight/*+[F]{#2}="parent"%
    @@{;"parent"**\dir{#1}}%
  }+UC}="\treename NODE\theXYTnode"%
  \XYTendbranch%
  \XYTmarkiffirst%
  \ignorespaces
}

%%
%% \fbranch[DIR]{LABEL}{FRAME}{<NODES>} -- make a branch with framed
%%                                         parent node and specified
%%                                         directionals for lines.
%%
%% Makes a branch. Parent node is decorated by a LABEL (Cf. \branch),
%% surrounded by a FRAME (in \Xy-Pic `\frm` syntax), directionals are
%% drawn with DIR (Cf. \branch).
%%
\newcommand{\cbranch}[4][-]{%
  \stepcounter{XYTnode}%
  \XYTleavegap%
  \XYTbeginbranch%
  \POS @+{*!U\xybox{%
    @i%
    #4%
    \POS;"first"**\dir{}%
    ?+/u\treeheight/*+[F#3]{#2}="parent"%
    @@{;"parent"**\dir{#1}}%
    }+UC}="\treename NODE\theXYTnode"%
  \XYTendbranch%
  \XYTmarkiffirst%
  \ignorespaces
}


%%
%% \begin{xytree}[NAME] <NODES> \end{xytree} -- typeset a tree-like structure
%% 
%% Typesets a tree-like structure, consisting of branches and leaves.
%% <NODES> is a whitespace separated list of \leaf and \branch
%% commands. NAME is used as a prefix for leaf and node names: all
%% leaves will have \Xy-Pic name "<prefix>LEAF<number>", where
%% <prefix> is NAME (defaults to "") and <number> starts from 1 (for
%% the leftmost leaf) and increases left-to-right; nodes will be named
%% "<prefix>NODE<number>" where <number> starts from 1 (at the root of
%% the tree), and increases in a left-to-right, up-to-down fashion.
%%
\newenvironment{xytree}[1][]{%
  \def\treename{#1}%
  \setcounter{XYTnode}{0}%
  \setcounter{XYTleaf}{0}%
  \xdef\XYTfirststack{}%
  \XYTfirsttrue%
  \begin{xy}%
  \ignorespaces
}{%
  \end{xy}%
}

\def\xytreec#1\endxytreec{%
  \setcounter{XYTnode}{0}%
  \setcounter{XYTleaf}{0}%
  \xdef\XYTfirststack{}%
  \XYTfirsttrue%
  {\xyc#1\endxyc}
}

%\def\XYTxyc{\xy*!C\xybox}
%\newenvironment{xytreec}[1][]{%
%  \def\treename{#1}%
%  \setcounter{XYTnode}{0}%
%  \setcounter{XYTleaf}{0}%
%  \xdef\XYTfirststack{}%
%  \XYTfirsttrue%
%  \expandafter\XYTxyc\bgroup%
%  \ignorespaces
%}{%
%  \egroup\endxy%
%}

%\begingroup% preserve \lccodes
%\lccode`\(=`\{% \catcode`\(=11%
%\lccode`\)=`\}% \catcode`\)=11%
%\lowercase{%
%  \gdef\beginxytreec#1\end(xytreec){%
%    \setcounter{XYTnode}{0}%
%    \setcounter{XYTleaf}{0}%
%    \xdef\XYTfirststack{}%
%    \XYTfirsttrue%
%    {\xyc#1\endxyc}
%    \end{xytreec}
%    }
%  }
%\endgroup
%\show\beginxytreec
%\newenvironment{xytreec}[1][]{%
%  \def\treename{#1}%
%  \beginxytreec%
%}{%
%}

% restore LaTeX default for .sty files
\makeatletter